package huadi.algorithm.sort;

/**
 * QuickSort 快速排序
 * 
 * @author Huadi
 */
public class QuickSort {
	public static void sort(int[] array) {
		sortInside(array, 0, array.length - 1);
	}

	private static void sortInside(int[] array, int beginIndex, int endIndex) {
		if (beginIndex >= endIndex) {
			return;
		}
		int pivot = array[beginIndex];
		int firstPointer = beginIndex + 1, lastPointer = endIndex;
		while (firstPointer < lastPointer) {
			while (firstPointer < lastPointer && pivot <= array[lastPointer]) {
				lastPointer--;
			}
			while (firstPointer < lastPointer && pivot > array[firstPointer]) {
				firstPointer++;
			}
			swap(array, firstPointer, lastPointer);
		}
		int finalIndex = firstPointer <= lastPointer ? firstPointer
				: lastPointer;

		// 对 pivot 本身即为最小值时进行处理.
		// 如数组为 {1, 2, 3} 时, pivot 值为 1, finalIndex 为 1.
		// 如果不加判断, 会交换数组中 1 和 2 的位置, 使排序数组变为 {2, 1, 3}.
		if (pivot > array[finalIndex]) {
			swap(array, beginIndex, finalIndex);
		} else {
			finalIndex--;
		}
		sortInside(array, beginIndex, finalIndex - 1);
		sortInside(array, finalIndex + 1, endIndex);
	}

	private static void swap(int[] array, int firstIndex, int lastIndex) {
		int temp = array[firstIndex];
		array[firstIndex] = array[lastIndex];
		array[lastIndex] = temp;
	}
}
